<?php

/**
 * 链式队列:只需要操作队头和队尾的指针
 */

//节点对象:一个正常的链表结构
class LinkQueueNode {
    public $data;
    public $next;
}

//队列对象
class LinkQueue {
    public $first; // 队头指针
    public $rear; // 队尾指针
}

function InitLinkQueue() {
    $node = new LinkQueueNode();
    $node->next = NULL;
    $queue = new LinkQueue();
    $queue->first = $node;
    $queue->rear = $node;
    return $queue;
}

//入队
function EnLinkQueue(LinkQueue &$queue, $e) {
    $node = new LinkQueueNode();
    $node->data = $e;
    $node->next = NULL;

    $queue->rear->next = $node;
    $queue->rear = $node;
}

//出队
function DeLinkQueue(LinkQueue &$queue) {
    if ($queue->first == $queue->rear) {
        return false;
    }

    $node = $queue->first->next;
    $v = $node->data;

    $queue->first->next = $node->next;
    if ($queue->rear == $node) {
        $queue->rear = $queue->first;
    }

    return $v;
}

$q = InitLinkQueue();
EnLinkQueue($q, 'A');
EnLinkQueue($q, 'B');
EnLinkQueue($q, 'C');
EnLinkQueue($q, 'D');
EnLinkQueue($q, 'E');

print_r($q);
/*
LinkQueue Object
(
    [first] => LinkQueueNode Object
        (
            [data] =>
            [next] => LinkQueueNode Object
                (
                    [data] => A
                    [next] => LinkQueueNode Object
                        (
                            [data] => B
                            [next] => LinkQueueNode Object
                                (
                                    [data] => C
                                    [next] => LinkQueueNode Object
                                        (
                                            [data] => D
                                            [next] => LinkQueueNode Object
                                                (
                                                    [data] => E
                                                    [next] =>
                                                )

                                        )

                                )

                        )

                )

        )

    [rear] => LinkQueueNode Object
        (
            [data] => E
            [next] =>
        )

)
*/

echo DeLinkQueue($q), PHP_EOL; // A
echo DeLinkQueue($q), PHP_EOL; // B

EnLinkQueue($q, 'F');
print_r($q);
/*
LinkQueue Object
(
    [first] => LinkQueueNode Object
        (
            [data] =>
            [next] => LinkQueueNode Object
                (
                    [data] => C
                    [next] => LinkQueueNode Object
                        (
                            [data] => D
                            [next] => LinkQueueNode Object
                                (
                                    [data] => E
                                    [next] => LinkQueueNode Object
                                        (
                                            [data] => F
                                            [next] =>
                                        )

                                )

                        )

                )

        )

    [rear] => LinkQueueNode Object
        (
            [data] => F
            [next] =>
        )

)
*/

echo "================================================== \n";

//用PHP自带的方法实现队列操作
$sqQueueList = [];
array_push($sqQueueList, 'a');
array_push($sqQueueList, 'b');
array_push($sqQueueList, 'c');
print_r($sqQueueList);
/*
Array
(
    [0] => a
    [1] => b
    [2] => c
)
*/

array_shift($sqQueueList);
array_shift($sqQueueList);
print_r($sqQueueList);
/*
Array
(
    [0] => c
)
*/